import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * @author LKQ
 * @date 2022/2/21 17:11
 * @description
 */
public class FormalSolution {
    public static void main(String[] args) {
        FormalSolution solution = new FormalSolution();
        int[] arr = {1024,512,256,128,64,32,16,8,4,2,1};
        solution.sortByBits(arr);
    }
    public int[] sortByBits(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int x: arr) {
            list.add(x);
        }
        // 预处理，使得查找时可以在线性时间内查询得知
        int[] bit = new int[10001];
        for (int i = 0; i <= 10000; i++) {
            bit[i] = bit[i >> 1] + (i & 1);
        }
        Collections.sort(list, (x, y) -> {
            if (bit[x] != bit[y]) {
                return bit[x] - bit[y];
            }else {
                return x - y;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
}
